package com.atguigu.search;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
//        int[] arr={1,3,4,5,22,35,35,35,35,35,35,35,44,57,122};
//
////        int search = search(arr, 0, arr.length - 1, 55);
////        System.out.println("resIndex="+search);
//        int[] searchAll = searchAll(arr, 0, arr.length - 1, 35);
//        System.out.println("resultIndexArr="+ Arrays.toString(searchAll));

        int[] arr={28, 180, 247, 279, 463, 483, 574, 596, 651, 709, 752, 1068, 1231, 1266, 1332, 1534, 1706, 1732, 1768, 1780, 1825, 1846, 1996, 2068, 2144, 2326, 2347, 2562, 2710, 2769};
        int search = search(arr, 0, arr.length - 1, 2068);
        System.out.println("resIndex="+search);
    }

    public static int searchCount=1;

    public static int search(int[] arr,int left,int right,int findVal){
        System.out.println("递归次数:"+searchCount++);

        int midIndex = (left + right) / 2;
        int midVal=arr[midIndex];

        if(left>right){
            return -1;
        }

        if(findVal>midVal){
            return search(arr,midIndex+1,right,findVal);
        }
        if(findVal<midVal){
            return search(arr,left,midIndex-1,findVal);
        }
        return midIndex;

    }

    public static int[] searchAll(int[] arr,int left,int right,int findVal){
        int midIndex = (left + right) / 2;
        int midVal=arr[midIndex];

        if(left>right){
            return new int[0];
        }

        if(findVal>midVal){
            return searchAll(arr,midIndex+1,right,findVal);
        }
        if(findVal<midVal){
            return searchAll(arr,left,midIndex-1,findVal);
        }
        int tempIndex=midIndex-1;
        int[] tempIndexArr=new int[arr.length];
        int resultCount=0;

        while(tempIndex>=0&&arr[tempIndex]==findVal){
            tempIndexArr[resultCount++]=tempIndex--;
        }

        tempIndexArr[resultCount++]=midIndex;

        tempIndex=midIndex+1;
        while(tempIndex<=arr.length-1&&arr[tempIndex]==findVal){
            tempIndexArr[resultCount++]=tempIndex++;
        }



        int[] resultIndexArr=new int[resultCount];
        for (int i = 0; i < resultCount; i++) {
            resultIndexArr[i]=tempIndexArr[i];
        }
        return resultIndexArr;

    }
}
